#define _CRT_SECURE_NO_WARNINGS 1
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        if (A == NULL)return false;
        if (A->next == NULL)return true;
        ListNode* star = A;
        ListNode* end = A;
        ListNode* cur = A;
        int num = 1;
        while (end->next != NULL) {
            end = end->next;
            num++;
        }
        if (num <= 3) {
            if (star->val == end->val)return true;
            else return false;
        }
        int k = num / 2;
        int f = num % 2 == 0 ? 0 : 1;
        int cnt = 1;
        ListNode* pre = NULL;
        ListNode* last = A->next;

        while (cnt <= k) {
            cnt++;
            cur->next = pre;
            pre = cur;
            cur = last;
            if (last)last = last->next;
        }
        ListNode* star1 = pre;
        ListNode* star2 = cur;
        if (f) {
            if (star2)star2 = star2->next;
        }
        while (star1 && star2) {
            if (star1->val != star2->val)return false;
            star1 = star1->next;
            star2 = star2->next;
        }
        return true;

    }
};